package 中等.贪心思想;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。
 * 请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。
 * 你可以返回任何满足该要求的答案，此题保证存在答案。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/distant-barcodes
 */
public class 距离相等的条形码_1054 {

    public static void main(String[] args) {

    }

    /**
     * 贪心思想+优先队列
     * 每次选取和前面一个条形码不相同且数量最多的条形码
     */
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int barcode : barcodes) {
            map.put(barcode, map.getOrDefault(barcode, 0) + 1);
        }
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            priorityQueue.add(new int[]{entry.getKey(), entry.getValue()});
        }
        int pre = -1;
        for (int i = 0; i < barcodes.length; i++) {
            int[] one = priorityQueue.poll();
            if (one[0] == pre) {
                int[] two = priorityQueue.poll();
                barcodes[i] = two[0];
                two[1]--;

                if (two[1] > 0) {
                    priorityQueue.add(two);
                }
            } else {
                barcodes[i] = one[0];
                one[1]--;
            }
            if (one[1] > 0) {
                priorityQueue.add(one);
            }
            pre = barcodes[i];
        }
        return barcodes;
    }

    /**
     * 计数统计
     * 放置思路，将相同的条形码隔一个空位放置，特殊情况，如果
     * 是奇数个条形码，且其中的某个条形码数量为 n/2+1，那么
     * 这个条形码必须放置在每个索引的偶数位，那么先将条形码
     * 按照数量排序，先放置在索引的偶数位，然后放奇数位
     * <p>
     * 优化：统计条形码数量之后不需要排序，只需要判断数量超过了总量的一半，
     * 如果没有优先放置奇数位，偶数位留给数量最多的条形码
     */
    public int[] rearrangeBarcodes2(int[] barcodes) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int barcode : barcodes) {
            map.put(barcode, map.getOrDefault(barcode, 0) + 1);
        }
        int idx = 0;
        int[][] record = new int[map.size()][2];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            record[idx] = new int[]{entry.getKey(), entry.getValue()};
            idx++;
        }
        Arrays.sort(record, (a, b) -> b[1] - a[1]);
        idx = 0;
        for (int i = 0; i < barcodes.length; i += 2) {
            barcodes[i] = record[idx][0];
            record[idx][1]--;

            if (record[idx][1] == 0) {
                idx++;
            }
        }
        for (int i = 1; i < barcodes.length; i += 2) {
            barcodes[i] = record[idx][0];
            record[idx][1]--;

            if (record[idx][1] == 0) {
                idx++;
            }
        }
        return barcodes;
    }

}
